package mySort;
//堆排序, 时间复杂度O(nlogn);
public class HeapSort {
    public void heapSort(int[] heap) {
        //先构造大根堆
        createMaxHeap(heap);
        //开始排序
        int end = heap.length - 1;
        while (end >= 0) {
            int tmp = heap[0];
            heap[0] = heap[end];
            heap[end] = tmp;
            shiftDown(heap, 0, end);
            end--;
        }
    }

    private void createMaxHeap(int[] heap) {
        for (int i = (heap.length - 2) / 2; i >= 0 ; i--) {
            shiftDown(heap, i, heap.length);
        }
    }

    //向下调整
    private void shiftDown(int[] heap, int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && heap[child] < heap[child+1]) {
                child++;
            }
            if (heap[child] > heap[parent]) {
                int tmp = heap[child];
                heap[child] = heap[parent];
                heap[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
         }
    }

}
